#include<stdio.h>
#include<stdlib.h>

typedef char Type;
#define MaxSize 50

typedef struct node
{
	Type data;
	struct node* lchild;
	struct node* rchild;
}BTNode;

BTNode* Init()
{
	BTNode* bt = (BTNode*)malloc(sizeof(BTNode));
	if (bt == NULL)
	{
		perror("fail");
		exit(1);
	}
	bt->data = 0;
	bt->lchild = bt->rchild = NULL;
	return bt;
}

void CreateBTree(BTNode** b, char* str)
{
	BTNode* St[MaxSize], * p = NULL;
	
	int top = -1, k = 0, j = 0;
	char ch;
	*b = NULL;
	ch = str[j];

	while (ch != '\0')
	{
		switch (ch)
		{
		case '(':
			top++;
			St[top] = p;
			k = 1;
			break;
		case ')':
			top--;
			break;
		case ',':
			k = 2;
			break;
		default:
			p = (BTNode*)malloc(sizeof(BTNode));
			if (p == NULL)
			{
				perror("fail");
				return;
			}
			p->data = ch;
			p->lchild = p->rchild = NULL;
			if (*b == NULL)
			{
				*b = p;
			}
			else
			{
				switch (k)
				{
				case 1:
					St[top]->lchild = p;
					break;
				case 2:
					St[top]->rchild = p;
					break;
				}
			}
		}
		j++;
		ch = str[j];
	}
}

void DestroyBT(BTNode** bt)
{
	if (*bt != NULL)
	{
		DestroyBT(&(*bt)->lchild);
		DestroyBT(&(*bt)->rchild);
		free(*bt);
		*bt = NULL;
	}
}

void DispBTree(BTNode* b)
{
	if (b != NULL)
	{
		printf("%c", b->data);
		if (b->lchild != NULL || b->rchild != NULL)
		{
			printf("(");
			DispBTree(b->lchild);
			if (b->rchild != NULL)
			{
				printf(",");
			}
			DispBTree(b->rchild);
			printf(")");
		}
	}
	printf("\n");
}

void PrevOrder(BTNode* b)
{
	if (b == NULL)
	{
		return;
	}
	else
	{
		printf("%c", b->data);
		PrevOrder(b->lchild);
		PrevOrder(b->rchild);
	}
}

void InOrder(BTNode* b)
{
	if (b == NULL)
	{
		return;
	}
	else
	{
		InOrder(b->lchild);
		printf("%c", b->data);
		InOrder(b->rchild);
	}
}

void invertTree(BTNode** root)
{
	if (*root == NULL)
		return;

	BTNode* tmp = (*root)->lchild;
	(*root)->lchild = (*root)->rchild;
	(*root)->rchild = tmp;
	invertTree(&(*root)->lchild);
	invertTree(&(*root)->rchild);
}

int main()
{
	BTNode* bt;
	
	char str[] = "A(B(D(,G)),C(E,F))";
	CreateBTree(&bt, str);

	//DispBTree(bt);

	/*PrevOrder(bt);
	printf("\n");

	InOrder(bt);*/

	invertTree(&bt);
	PrevOrder(bt);
	printf("\n");

	InOrder(bt);

	DestroyBT(&bt);

	return 0;
}